// 给定链表头节点head，返回链表的中间节点，如果有两个中间节点，则返回第二个中间节点

// 思路：快慢指针，快指针每次走2步，慢指针每次走1步，则快指针为空或者走到最后的时候，慢指针正好是n / 2的中间位置
// 时间复杂度：O(n)
// 空间复杂度：O(1)

const { LinkedList, ListNode} = require('./64.设计链表')

function middleNode(head) {
    let slow = head
    let fast = head
    while (fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
    }
    return slow
}


let list = new LinkedList([2, 5, 1, 7, 3, 9])
console.log(middleNode(list.head))
